#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
#define MaxSize 50
//栈  在栈顶进行插入和删除，后进先出
//顺序栈
//声明顺序栈的类型
typedef struct
{
    ElemType data[MaxSize];//存放栈的数据元素
    int top; //栈顶指针
}SqStack;  //顺序栈类型
//栈到顺序栈的映射  a1,a2```an------>a1-0,a2-1,````an-1-MaxSize-1,n-1-top
//栈空条件：s->top==-1 //s为栈指针
//栈满条件：s->top==MaxSize-1
//进栈操作：栈顶指针top+1.将元素e放在栈顶指针处
//出栈操作：将栈顶指针top处元素取出给e，将栈顶指针-1
//初始化栈
void InitStack(SqStack *&s)
{
    s=(SqStack *)malloc(sizeof(SqStack));
    s->top=-1;
}
//销毁栈
void DestroyStack(SqStack *&s)
{
    free(s);//直接释放s栈指针的内存空间
}
//判断栈是否为空
void StackEmpty(SqStack *s)
{
    return(s->top==-1);
}
//进栈
bool Push(SqStack *&s,ElemType e)
{
    if(s->top==MaxSize-1)
        return false;//判断是否栈满
    s->top++;//栈顶指针+1
    s->data(s->top)=e;
    return true;
}
//出栈
bool Pop(SqStack *&s,ElemType &e)
{
    if(s->top==-1)
        return false;//判断栈为空
    e=s->data[s->top];//取栈顶元素
    s->top--;//栈顶指针-1
    return true;
}
//取栈顶元素
bool GetTop(SqStack *s,ElemType e)
{
    if(s->top==-1)
        return false;//判断栈为空
    e=s->data[s->top];
    return true;
}
//共享栈
//两个数组，两个栈，有两个栈底，一个做始端，一个做末端，a1,a2```an bm,```` b2,b1
//栈空条件：top1==-1,top2==MaxSize
//栈满条件：top1==top2-1
//进栈操作：进栈1 top1++;data[top1]=x;进栈2 top2--;data[top2]=x;
//出栈操作：出栈1 x=data[top1];top1--;出栈2 data[top2]=x;top2++
//声明共享栈
typedef struct{
    ElemType data[MaxSize];
    int top1,top2;
}DStack;
//链栈
//声明链栈
typedef struct linknode{
    ElemType data;//数据域
    struct linknode *next;//指针域
}LinkStNode;//结点类型
//s为头结点指针
//栈空条件：s->next==NULL
//进栈操作：新建结点存放e（由p指向），将p插入头结点之后
//出栈操作：取出首节点的data值删除
//初始化栈
void InitStack1(LinkStNode *&s)
{
    s=(LinkStNode *)malloc(sizeof(LinkStNode));
    s->next=NULL;
}
//销毁栈
void DestroyStack1(LinkStNode *&s)
{
    LinkStNode *pre=s,*p=s->next;
    while(p!=NULL)
    {
        free(pre);
        pre=p;
        p=pre->next;
    }
}
//判断是否为空
void StackEmpty1(LinkStNode *s)
{
    return(s->next==NULL);
}
//进栈
bool Push1(LinkStNode *&s,ElemType e)
{
    LinkStNode *p;
    p=(LinkStNode *)malloc(sizeof(LinkStNode));//新建结点p
    p->data=e;
    p->next=s->next;
    s->next=p;
    return true;
}
//出栈
bool Pop1(LinkStNode *&s,ElemType e)
{
    LinkStNode *p;
    if(s->next==NULL)
        return false;
    p=s->next;
    e=p->data;
    s->next=p->next;
    free(p);
    return true;
}
//取栈顶元素
bool GetTop1(LinkStNode *s,ElemType e)
{
    if(s->next==NULL)
        return false;
    e=s->next->data;
    return true;
}
int main()
{
    ElemType e;
    SqStack *s;
    printf("基本运算：\n");
    printf("1.初始化栈\n");
    InitStack(s);
    printf("2.栈为:%s\n",(StackEmpty(s)?"空":"非空"));
    printf("3.依次进栈：\n");
    Push(s,'1');
    Push(s,'2');
    Push(s,'3');
    Push(s,'4');
    Push(s,'5');
    printf("4.栈为：%s\n",(StackEmpty(s)?"空":"非空"));
    printf("5.出栈序列：");
    while(!StackEmpty(s))
    {
        Pop(s,e);
        printf("%c",e);
    }
    printf("\n");
    printf("6.栈为：%s\n",(StackEmpty(s)?"空":"非空"));
    printf("7.释放栈\n");
    DestroyStack(s);
    return 1;
}